// ============================================================================
//
// Graph framework by Aurelien Moreau aurelien.moreau@gmail.com
// Modified by Pierre CHATEL chatelp@gmail.com
// Distributed under LGPL
// Copyright (C) Aurelien Moreau, 2008, 2009. All rights reserved
//
// ============================================================================

package com.thalesgroup.graphFramework.sortMethods;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;

import com.thalesgroup.graphFramework.core.Graph;
import com.thalesgroup.graphFramework.core.Vertex;
import com.thalesgroup.graphFramework.searchMethods.DepthFirstSearch;

public class TopologicalSort {

	/**
	 * Sort graph's nodes topologicaly.
	 * 
	 * @param graph
	 *            the graph to process.
	 * @return the sorted nodes (no side-effects on the graph itself, only on
	 *         nodes' meta-data).
	 */
	public static <S, T> Vertex<S, T>[] sort(Graph<S, T> graph) {
		DepthFirstSearch.search(graph);

		ArrayList<Vertex<S, T>> vertices = new ArrayList<Vertex<S, T>>();
		for (Iterator<Vertex<S, T>> vi = graph.getVertices(); vi.hasNext();) {
			vertices.add(vi.next());
		}

		// Sort nodes according to added meta-data
		Collections.sort(vertices,
				new ProcessedDateReverseOrderComparator<S, T>());

		// Return sorted nodes
		Vertex<S, T> array[] = new Vertex[vertices.size()];
		return vertices.toArray(array);
	}
}
